/*
 * shingletypes.cpp
 *
 *  Created on: Jun 6, 2011
 *      Author: timothy
 */

#include <time.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

using namespace::std;

#include "shingletypes.h"
#include "debug.h"
#include "shinglehashtable.h"

#define MAX32 4294967296
#define HASH_CONSTANT 4294967291 // 2^32 - 5 is prime

// SHINGLE CONTEXT //

extern arg_vars *g_ArgVars;
extern ShingleContext *g_ShingleContext;
extern double allocTimes[];
extern int numAllocs[];

ShingleContext::ShingleContext()
{
	//srand(time(NULL));
	srand(0);
	large_prime = 2147483647; //2^31 - 1 is prime. How'bout that?
	s = g_ArgVars->shingle_length; // From args
	c = g_ArgVars->num_trials; // From args
	r1 = (unsigned long int*)calloc(c, sizeof(long int));
	r2 = (unsigned long int*)calloc(c, sizeof(long int));
	for(unsigned int i = 0; i < c; ++i)
	{
		r1[i] = (((unsigned long int)rand()+MAX32*rand())%large_prime);
		r2[i] = (((unsigned long int)rand()+MAX32*rand())%large_prime);
	}
	MinimumAlignment = .775;
	if(MinimumAlignment > (double)(s-1)/s)
		MinimumAlignment = (double)(s-1)/(s+2); // Low enough that having all but one match is good.

	ShingleAllocs = (Shingle**)calloc(omp_get_max_threads(), sizeof(Shingle*));
	UnusedShingles = (int*)calloc(omp_get_max_threads(), sizeof(int));
	for(unsigned int i = 0; i < s; ++i)
	{
		hashConstant[i] = rand();
	}
	for(int i = 0; i < omp_get_max_threads(); ++i)
	{
		ShingleAllocs[i] = 0;
		UnusedShingles[i] = 0;
	}
}
ShingleContext::~ShingleContext()
{
	free(r1);
	free(r2);
}

int ShingleContext::Hash(char *string)
{
	int sum = 0;
	for(int i = 0; i < 40; ++i)
	{
		sum += string[i] * g_ShingleContext->hashConstant[i];
		sum %= large_prime;
	}
	return sum;
}

// VERTEX //

void Vertex::InitVertex(char *line)
{
// Line is of the form v#e,e,e,e,e,e,e,
	Neighbors = new NeighborList();
	char *tokBuf = (char*)malloc(sizeof(char*));
	char *memBuf = tokBuf;
//	pdprint(PDPRINT_VERTEX | PDPRINT_HASH, "Creating vertex: %s", line);
	char *tok = strtok_r(line, "#", &tokBuf);
	ID = atoi(tok);
	if(ID < 0)
		pdprint(PDPRINT_ALL, "Error in vertex construction (ID = %d)\n", ID);
#ifdef SELF_SELF_EDGES
	Neighbors->Push(ID);
#endif
	tok = strtok_r(NULL, ",", &tokBuf);
	while(tok)
	{
		int neigh = atoi(tok);
		if(neigh == ID)
			pdprint(PDPRINT_ALL, "Self-self edge detected!\n");
		if(neigh < 0) pdprint(PDPRINT_ALL, "Error in vertex construction (Neighbor = %d)\n", neigh);
		Neighbors->Push(neigh);
		tok = strtok_r(NULL, ",", &tokBuf);
	}
//	pdprint(PDPRINT_VERTEX, "Created vertex of ID %d and Size %d\n", ID, Neighbors->Size());
	free(memBuf);
}

// This function adds edges to any missing (ID = -1) vertices on the graph and
//   returns the total number of edges * 2.
int Vertex::Repair(Vertex *graph)
{
	if(this->ID == -1) return 0;
	int ret = 0;
	NeighborListEntry *iter = Neighbors->StartIterator();
	while(iter)
	{

		unsigned long neigh = iter->value;
		if((long)neigh == ID)
		{
			iter = iter->next;
			continue;
		}
		if(graph[neigh].ID == -1)
		{
			if(graph[neigh].Neighbors == NULL)
				graph[neigh].Neighbors = new NeighborList();
			graph[neigh].Neighbors->Push(this->ID);
			++ret;
		}
		++ret;
		iter = iter->next;
	}
	return ret;
}
void Vertex::WriteGEL(FILE *out)
{
	fprintf(out, "%d#", ID);
	if(!Neighbors)
	{
		fprintf(out, "\n");
		return;
	}
	else
	{
		NeighborListEntry *iter = Neighbors->StartIterator();
		while(iter)
		{
			int neigh = iter->value;
			if(neigh == ID)
			{
				iter = iter->next;
				continue;
			}
			if(iter->next)
			{
				fprintf(out, "%d,", neigh);
			}
			else
			{
				fprintf(out, "%d\n", neigh);
			}
			iter = iter->next;
		}
	}
}


Vertex::Vertex(char *line)
{
	InitVertex(line);
}
Vertex::~Vertex()
{
	if(Neighbors) delete(Neighbors);
}
Shingle* Vertex::MakeShingle(int index, unsigned long hash)
{
#ifdef IGNORE_SMALL_TIMES
	if(this->Neighbors->Size() < g_ArgVars->shingle_length)
		return NULL;
	SLE_t topElems[g_ArgVars->shingle_length];
	Shingle *ret = Shingle::InitShingle(1, ID);
#else // NO IGNORE_SMALL_TIMES
	if(this->Neighbors->Size() < g_ArgVars->shingle_length)
		return NULL;
	SLE_t topElems[g_ArgVars->shingle_length];
	double t1, t2;
	t1 = omp_get_wtime();
	Shingle *ret = Shingle::InitShingle(1, ID);
	t2 = omp_get_wtime();
	int proc = omp_get_thread_num();
	allocTimes[proc] += t2 - t1;
#endif // IGNORE_SMALL_TIMES

#ifndef ANONYMOUS_SHINGLES
	Shingle::FindTopSElems(topElems, Neighbors, index);
	for(unsigned int i = 0; i < g_ShingleContext->s; ++i)
	{
		ret->hashkey *= g_ShingleContext->numVertices;
		ret->hashkey += topElems[i].value;
		//ret->hashkey %= g_ShingleContext->large_prime;
		ret->vertices[i] = topElems[i].vertex;
	}
#else
	ret->hashkey = hash;
#endif
	ret->nthShingle = index;

	return ret;
}
Vertex *Vertex::CreateVertex(char *line)
{
	if(strlen(line) > 0)
	{
		Vertex *ret = new Vertex(line);
		if(ret->Neighbors->Size() >= g_ShingleContext->s)
			return ret;
		else
		{
			delete(ret);
			return NULL;
		}
	}
	else
		return NULL;
}

// SHINGLE //

Shingle::Shingle(int type, unsigned long source)
{
	_firstNeighbor.value = source;
	ShingleType = type;
	hashkey = 0;
	Neighbors = &_neighborListInner;
	Neighbors->tail = &_firstNeighbor;
	neighborCount = 1;

#ifndef ANONYMOUS_SHINGLES
	//vertices = (int*)calloc(g_ShingleContext->s, sizeof(int));
#endif

	memCount = 1;
	isMemoryBlock = 2;
	//omp_init_lock(&lock);
}
Shingle* Shingle::InitShingle(int type, unsigned long source)
{
#ifndef BULK_ALLOCATE_SHINGLES
	return new Shingle(type, source);
#else
	numAllocs[omp_get_thread_num()] += 1;
	Shingle *init = AllocateShingle();
	init->ShingleType = type;
	init->hashkey = 0;
	init->_firstNeighbor.value = source;
	init->Neighbors = &init->_neighborListInner;
	init->_neighborListInner.size = 1;
	init->Neighbors->tail = &init->_firstNeighbor;
	init->Neighbors->head = &init->_firstNeighbor;
	init->neighborCount = 1;
	//init->vertices = (int*)calloc(g_ShingleContext->s, sizeof(int));
	//init->omp_init_lock(&lock);
	return init;
#endif
}
Shingle::~Shingle()
{
	// This destructor is called only from ClearData.
	// It does not need to do anything at this time.
}
void Shingle::ClearData()
{
#ifndef ANONYMOUS_SHINGLES
//	if(vertices)
//		free(vertices);
//	vertices = 0;
#endif

	if(Neighbors)
		Neighbors->ClearData();
	if(isMemoryBlock == 1) // 1 if it was malloc'd
	{
		if(memCount == 0)
			free(this);
	}
	else if(isMemoryBlock == 2) // 2 if it was created by the constructor
	{
		delete(this);
	}
	else // 0 if it was part of another malloc
	{
		parentBlock->memCount--;
		if(parentBlock->memCount == 0)
			free(parentBlock);
	}
}
Shingle *Shingle::MakeShingle(int index, unsigned long hash)
{
	if(this->neighborCount < g_ArgVars->shingle_length)
	{
//		pdprint(PDPRINT_SHINGLE, "Shingle culled due to too few neighbors.\n");
		return NULL;
	}
	Shingle *ret = InitShingle(2, hashkey);

#ifndef ANONYMOUS_SHINGLES
	SLE_t topElems[g_ArgVars->shingle_length];
	FindTopSElems(topElems, Neighbors, index);
	for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
	{
		ret->hashkey *= g_ShingleContext->numVertices;
		ret->hashkey += topElems[i].value; // * g_ShingleContext->hashConstant[i];
		//ret->hashkey %= g_ShingleContext->large_prime;
		ret->vertices[i] = topElems[i].vertex;
	}
#else
	ret->hashkey = hash;
#endif
//	pdprint(PDPRINT_SHINGLE_2, "  Created shingle %d for shingle %ld as %ld\n", index, hashkey, ret->hashkey);
//	pdprint(PDPRINT_SHINGLE_2, "  Composition: %d, %d, %d, %d\n", ret->vertices[0], ret->vertices[1], ret->vertices[2], ret->vertices[3]);
	ret->nthShingle = index;
//	ret->ShingleNeighbors.push_back(this->hashkey); This is done in the constructor.

	return ret;
}
int Shingle::CompareTo(Shingle *other)
{
	if(this == NULL) { pdprint(PDPRINT_ALL, "Cannot compare NULL to a shingle.\n"); return -1; }
	if(this->nthShingle != other->nthShingle) return this->nthShingle - other->nthShingle;
	return(hashkey - other->hashkey);
}
double Shingle::AlignmentTo(Shingle *other)
{
#ifdef ANONYMOUS_SHINGLES
	return 1.0;
#else
	if(this == NULL || other == NULL) { pdprint(PDPRINT_ALL, "Cannot align NULL with shingle.\n"); return -1; }
	int aligned = 0; int unaligned = 0;
	for(unsigned int i = 0; i < g_ShingleContext->s; ++i)
	{
		int isAligned = 0;
		for(unsigned int j = 0; j < g_ShingleContext->s; ++j)
		{
			if(this->vertices[i] == other->vertices[j])
			{
				isAligned = 1;
				break;
			}
		}
		if(isAligned)
			aligned++;
		else
			unaligned++;
	}
	double ret = (double)aligned / (aligned+unaligned);
//	pdprint(PDPRINT_CURRENTBUG, "Alignment between (%d %d) and (%d %d) returned %lf\n", vertices[0], vertices[1], other->vertices[0], other->vertices[1], ret);
	return ret;
#endif
}
int Shingle::VerifyNeighbor(Vertex *item)
{
	int align = g_ArgVars->shingle_length;
	NeighborListEntry *iter = item->Neighbors->StartIterator();
	while(iter)
	{
		long value = iter->value;
		for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
		{
			if(value == this->vertices[i])
			{
				align--;
				break;
			}
		}
		iter = iter->next;
	}
	if(align != 0)
	{
		pdprint(PDPRINT_ALL, "Impossible neighbor detected!\n");
#pragma omp critical(PDPRINT)
		{
			iter = item->Neighbors->StartIterator();
			while(iter)
			{
				fprintf(stderr, "%ld, ", iter->value);
				iter = iter->next;
			}
			fprintf(stderr, "\n");
			for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
			{
				fprintf(stderr, "%d, ", this->vertices[i]);
			}
			fprintf(stderr, "\n");
			Shingle *otherShingle = item->MakeShingle(this->nthShingle, 0);
			fprintf(stderr, "Collision on ");
			for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
			{
				fprintf(stderr, "%d, ", otherShingle->vertices[i]);
			}
			fprintf(stderr, "\n");
			fflush(stderr);
			unsigned long otherKey = otherShingle->hashkey;
			if(otherKey == this->hashkey)
				fprintf(stderr, "Key collision!\n");
			DeallocateShingle();

			fflush(stderr);
			exit(1);
		}
	}
	return (align==0);
}

Shingle *Shingle::AllocateShingle()
{
#ifdef BULK_ALLOCATE_SHINGLES
	int proc = omp_get_thread_num();
	int shinglesLeft = g_ShingleContext->UnusedShingles[proc];
	if(shinglesLeft == 0)
	{
		// Allocate more shingles
		shinglesLeft = SHINGLE_CHUNK;
		g_ShingleContext->UnusedShingles[proc] = shinglesLeft;
		g_ShingleContext->ShingleAllocs[proc] = (Shingle*)calloc(SHINGLE_CHUNK, sizeof(Shingle));
	}
	int index = SHINGLE_CHUNK - shinglesLeft;
	g_ShingleContext->UnusedShingles[proc]--;
	if(index == 0)
	{
		g_ShingleContext->ShingleAllocs[proc][0].isMemoryBlock = 1;
		g_ShingleContext->ShingleAllocs[proc][0].parentBlock = 0;
		g_ShingleContext->ShingleAllocs[proc][0].memCount = SHINGLE_CHUNK;
	}
	else
	{
		g_ShingleContext->ShingleAllocs[proc][index].isMemoryBlock = 0;
		g_ShingleContext->ShingleAllocs[proc][index].parentBlock = g_ShingleContext->ShingleAllocs[proc];
	}
	return &g_ShingleContext->ShingleAllocs[proc][index];
#else
	return NULL;
#endif
}
void Shingle::DeallocateShingle()
{
	int proc = omp_get_thread_num();
	++g_ShingleContext->UnusedShingles[proc];
}

unsigned long Shingle::MakeKey(Shingle *shingle, int index)
{
	SLE_t topElems[g_ArgVars->shingle_length];
	FindTopSElems(topElems, shingle->Neighbors, index);

	unsigned long retHashkey = 0;
	for(unsigned int i = 0; i < g_ShingleContext->s; ++i)
	{
		retHashkey *= g_ShingleContext->numVertices;
		retHashkey += topElems[i].value; // * g_ShingleContext->hashConstant[i];
		//retHashkey %= g_ShingleContext->large_prime;
	}

	return retHashkey;
}
unsigned long Shingle::MakeKey(Vertex *vertex, int index)
{
	SLE_t topElems[g_ArgVars->shingle_length];
	FindTopSElems(topElems, vertex->Neighbors, index);

	unsigned long retHashkey = 0;
	for(unsigned int i = 0; i < g_ShingleContext->s; ++i)
	{
		retHashkey *= g_ShingleContext->numVertices;
		retHashkey += topElems[i].value; // * g_ShingleContext->hashConstant[i];
		//retHashkey %= g_ShingleContext->large_prime;
	}

	return retHashkey;
}
inline void InitSLE_t(SLE_t *out, unsigned long value, int nthShingle)
{
	unsigned long from = value;
	value *= g_ShingleContext->r1[nthShingle];
	value %= g_ShingleContext->large_prime;
	value += g_ShingleContext->r2[nthShingle];
	value %= g_ShingleContext->large_prime;
	*out = SLE_t(from, value);
}


void Shingle::FindTopSElems(SLE_t *ret, NeighborList *neighbors, int nthShingle)
{
	NeighborListEntry *iter = neighbors->StartIterator();
	unsigned int neighSize = neighbors->Size();
	SLE_t temp;

	int lowestIndex = -1;

	for(unsigned int i = 0; i < neighSize; ++i)
	{
		InitSLE_t(&temp, iter->value, nthShingle);
		iter = iter->next;
		if(i < g_ShingleContext->s)
		{
			ret[i] = temp;
		}
		else
		{
			if(lowestIndex == -1) // Recalculate the lowest
			{
				lowestIndex = 0;
				for(unsigned int j = 1; j < g_ShingleContext->s; ++j)
				{
					if(ret[j] < ret[lowestIndex])
						lowestIndex = j;
				}
			}
			if(temp > ret[lowestIndex]) // Higher than the lowest
			{
				ret[lowestIndex] = temp;
				lowestIndex = -1;
			}
		}
	}
	// Slugsort ret
	unsigned int maxI = g_ShingleContext->s - 1;
	for(unsigned int i = 0; i < maxI; ++i)
		for(unsigned int j = i+1; j < g_ShingleContext->s; ++j)
		{
			if(ret[i] > ret[j])
			{
				temp = ret[i];
				ret[i] = ret[j];
				ret[j] = temp;
			}
		}

//	// First, get the FIRST (not Top) S elems from the neighbors list.
//	NeighborListEntry *iter = neighbors->StartIterator();
//
//	for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
//	{
//		unsigned long int hash = iter->value;
//		hash *= g_ShingleContext->r1[nthShingle];
//		hash %= g_ShingleContext->large_prime;
//		hash += g_ShingleContext->r2[nthShingle];
//		hash %= g_ShingleContext->large_prime;
//		ret[i] = SLE_t(iter->value, hash);
//		iter = iter->next;
//	}
//
//	// Sort them
//	// Need to make this nln(n)
//	for(unsigned int i = 0; i < g_ArgVars->shingle_length-1; ++i)
//		for(unsigned int j = i + 1; j < g_ArgVars->shingle_length; ++j)
//		{
//			if(ret[j] < ret[i])
//			{
//				// Swap the two values
//				SLE_t sto = ret[i];
//				ret[i] = ret[j];
//				ret[j] = sto;
//			}
//		}
//
//	// Go down the neighbors list and find more elements, displacing others as appropriate.
//	while(iter)
//	{
//		unsigned long int hash = iter->value;
//		hash *= g_ShingleContext->r1[nthShingle];
//		hash %= g_ShingleContext->large_prime;
//		hash += g_ShingleContext->r2[nthShingle];
//		hash %= g_ShingleContext->large_prime;
//
//		for(unsigned int i = 0; i < g_ArgVars->shingle_length; ++i)
//		{
//			if(hash < ret[i].value)
//			{
//				for(unsigned int j = g_ArgVars->shingle_length-1; j > i; --j)
//				{
//					ret[j] = ret[j-1];
//				}
//				ret[i] = SLE_t(iter->value, hash);
//				break;
//			}
//		}
//		iter = iter->next;
//	}
//
//	if(DEBUG_LEVEL & PDPRINT_SHINGLE_3)
//	{
//		iter = neighbors->StartIterator();
//		int i = 0;
//		while(iter)
//		{
//			unsigned long int hash = iter->value;
//			hash *= g_ShingleContext->r1[nthShingle];
//			hash %= g_ShingleContext->large_prime;
//			hash += g_ShingleContext->r2[nthShingle];
//			hash %= g_ShingleContext->large_prime;
//			for(unsigned int j = 0; j < g_ArgVars->shingle_length; ++j)
//			{
//				if(hash == ret[j].value) break;
//				else if(hash < ret[j].value)
//				{
//					pdprint(PDPRINT_ALL, "Incorrect selection %ld (%d should be at %d).\n", hash, i, j);
//					break;
//				}
//			}
//			++i; iter = iter->next;
//		}
//	}
}
